package com.chj.jz.dp.class03;

public class Code02_HouseRobber {
	/**
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    public static long houseRobber(int[] A) {
        // write your code here
    	
    	int n = A.length;
    	if(n == 0) {
    		return 0;
    	}
    	
    	if(n == 1) {
    		return A[0];
    	}
    	
    	long[] f = new long[n + 1];
    	f[0] = 0;
    	f[1] = A[0];
    	f[2] = Math.max(A[0], A[1]);
    	for(int i =3; i <= n; i++) {
    		f[i] = Math.max(f[i - 1], f[i - 2] + A[i - 1]);
    	}
    	
    	return f[n];
    }
    
    public static void main(String[] args) {
		{
			int[] arr = new int[]{ 3, 8, 4 };
			System.out.println(houseRobber(arr));
		}
		{
			int[] arr = new int[]{ 5, 2, 1, 3 };
			System.out.println(houseRobber(arr));
		}
	}
}
